package com.yulan.xunfei;

import org.junit.Test;

import java.util.Scanner;

public class test2 {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {// 注意，如果输入是多个测试用例，请通过while循环处理多个测试用例
            int n = in.nextInt();
            int[] arr = new int[n];
            for(int i=0; i<n; i++){
                arr[i] = in.nextInt();
            }
            quickSort(arr,0,arr.length-1);

        }
    }

    public static void quickSort(int[] arr ,int l, int r){

        if(l>=r) return;


        int index = partition(arr,l,r);

        outArr(arr);

        quickSort(arr,l,index-1);
        quickSort(arr,index+1,r);


    }

    public static int partition(int[] arr, int l, int r){
        int povit = arr[l];
        while(l<r){
            while(l<r && arr[r] >= povit)
                r--;

            arr[l] = arr[r];

            while(l<r && arr[l] <= povit)
                l++;

            arr[r] = arr[l];


        }
        arr[l] = povit;

        return l;
    }

    public static void outArr(int[] arr){
        for(int i=0; i<arr.length; i++){
            System.out.print(arr[i]+" ");
        }
        System.out.println();
    }


    @Test
    public void test(){
        int[] arr = {25 ,84 ,21 ,47 ,15 ,27 ,68 ,35 ,20};
        int[] arr2 = {2,5,6,8,1,3,4,9,10,7};
        quickSort(arr,0,arr.length-1);

    }
}
